<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var postorderTraversal = function (root) {
        // 方法一：递归---时间O（n）（）---空间：O（n）（）
        // const stack = []
        // function postOrder(root) {
        //   if (!root) return
        //   postOrder(root.left)
        //   postOrder(root.right)
        //   stack.push(root.val)
        // }
        // postOrder(root)
        // return stack

        // 方法一：遍历（取巧）---时间O（n）（）---空间：O（2n）（）
        // 先用类似先序遍历的方式，按 根右左 的顺序将二叉树存入到一个栈中
        // 利用栈先进后出的特性，将这个栈逐个出栈，就实现了 左右根 的遍历了
        // const stack = [root]
        // const tempStack = []
        // const res = []
        // if (!root) return res
        // while (stack.length) {
        //   let a = stack.pop()
        //   tempStack.push(a)
        //   a.left && stack.push(a.left)
        //   a.right && stack.push(a.right)
        // }
        // while (tempStack.length) {
        //   let b = tempStack.pop()
        //   res.push(b.val)
        // }
        // return res

        // 方法一：遍历（正常写法）---时间O（n）（）---空间：O（n）（）
        const stack = [];
        const res = [];
        let prev = null;
        while (root || stack.length) {
          debugger;
          while (root) {
            stack.push(root);
            root = root.left;
          }
          root = stack.pop();
          // prev记录上一个有左右子节点的节点，当他第一次pop()的时候
          // 会再push到stack里面去，之后root = root.right，先去算right，并且用prev记录这个节点的right
          // 下次再把这个节点拿出来的时候root.right === prev就可以输出这个节点的值了
          if (root.right === null || root.right === prev) {
            res.push(root.val);
            prev = root;
            root = null;
          } else {
            stack.push(root);
            root = root.right;
          }
        }
        return res;
      };

      const obj = {
        val: 4,
        left: {
          val: 2,
          left: {
            val: 1,
            left: null,
            right: null,
          },
          right: {
            val: 3,
            left: null,
            right: null,
          },
        },
        right: {
          val: 7,
          left: {
            val: 6,
            left: null,
            right: null,
          },
          right: {
            val: 9,
            left: null,
            right: null,
          },
        },
      };
      console.log(postorderTraversal(obj));
    </script>
  </body>
</html>
